package shu;
import java.util.PriorityQueue;//优先队列
public class HFM {
    //构造哈夫曼树
    public HaffNode CreateHFM(char[] chars,int[] weight){
        PriorityQueue<HaffNode> nodes = new PriorityQueue<>();
        //将初始化节点加入队列中
        for (int i = 0; i < chars.length; i++) {
            nodes.add(new HaffNode(chars[i],weight[i]));
        }
        //构造过程
        while(nodes.size()>=2){
            //取2个权重最小的节点
            HaffNode min1=nodes.poll();
            HaffNode min2 = nodes.poll();
            //创建新节点，作为min1和min2的父节点；
            HaffNode parent = new HaffNode();
            parent.lchild=min1;
            parent.rchild = min2;
            parent.weight = min1.weight+min2.weight;
            //将新节点加入优先队列中
            nodes.add(parent);
        }
        return nodes.poll();
    }

    //打印哈夫曼
    public void printCode(HaffNode node,String currentCode){
        if(node!=null){
            //先序遍历，同时为叶子节点设置编码
            if(node.lchild==null && node.rchild==null){
                node.code=currentCode;
                System.out.println();
            }
        }else{
            printCode(node.lchild,currentCode+"0");
            printCode(node.rchild,currentCode+"1");
        }
    }

    public static void main(String[] args) {
        HFM hfm = new HFM();
        char[] chars = "ABCDEFGH".toCharArray();
        int [] weigth = {5,25,3,6,10,11,36,4};
       HaffNode root =hfm.CreateHFM(chars,weigth);
        hfm.printCode(root,"");
    }
}
